import java.util.*;

public class Solution212 {

    int[][] directArr = new int[][]{{0,1},{1,0},{0,-1},{-1,0}};

    boolean[][] occurArr;

    private List<String> getProbString(String[] words, Set<String> resSet){
        List<String> res = new ArrayList<>();
        for (String word:words) {
            if(!resSet.contains(word)){
                res.add(word);
            }
        }
        return res;
    }

    private boolean travel(char[][] board, String word, int m, int n, int loc){
        if(!(0<=m&&m< board.length&&0<=n&&n< board[0].length)){
            return false;
        }
        if(word.charAt(loc) != board[m][n]||occurArr[m][n]){
            return false;
        }
        if(loc == word.length()-1){
            return true;
        }
        occurArr[m][n] = true;
        for (int i = 0; i < directArr.length; i++) {
            int tmpM = m+directArr[i][0];
            int tmpN = n+directArr[i][1];
            if(travel(board, word, tmpM, tmpN, loc+1)){
                return true;
            }
        }
        occurArr[m][n] = false;
        return false;
    }

    public List<String> findWords(char[][] board, String[] words) {
        Set<String> res = new HashSet<>();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                List<String> tarWords = getProbString(words, res);
                if(tarWords.isEmpty()){
                    continue;
                }
                for (String word:tarWords) {
                    occurArr = new boolean[board.length][board[0].length];
                    if(travel(board, word, i, j, 0)){
                        res.add(word);
                    }
                }
            }
        }
        return new ArrayList<>(res);
    }

    public static void main(String[] args) {
        Solution212 s = new Solution212();
        System.out.println(s.findWords(new char[][]{{'a','b','c','e'},{'x','x','c','d'},{'x','x','b','a'}},
new String[]{"abc","abcd"}));
    }
}
